package com.yulongtian.algorithms.binarysearch01;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/special-array-with-x-elements-greater-than-or-equal-x/
 * 可
 *
 * @author yulongTian
 * @create 2023-02-06 11:31
 */
public class Test08 {
    public static void main(String[] args) {
        int[] nums = {0, 4, 3, 0, 4};
//        int[] nums = {3, 6, 7, 7, 0};
//        int[] nums = {3, 5};
//        int[] nums = {1, 1, 2};
        System.out.println(specialArray(nums));
    }

    //    //他人的方法，和我的方法一样，但是更加简洁
//    public int specialArray(int[] nums) {
//        int n = nums.length;
//        // 对于从0到n的每个数
//        for(int i = 0; i <= n; i++) {
//            // 设置计数器
//            int cnt = 0;
//            // 遍历数组中的每个元素
//            for(int num : nums) {
//                // 符合条件计数器加1
//                if(num >= i) cnt++;
//            }
//            // 若恰好有i个元素大于等于i，则返回该特征值
//            if(cnt == i) return i;
//        }
//        return -1;
//    }
    public static int specialArray(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        int[] cnt = new int[len + 1];
        for (int i = nums.length - 1, index = len; i >= 0; i--) {
            if (nums[i] >= index) {
                cnt[index]++;
            } else {
                if (index - 1 >= 0) {
                    cnt[index - 1] = cnt[index];
                    index--;
                } else {
                    break;
                }
                i++;
            }
            if (i == 0) {
                while (index > 0) {
                    cnt[index - 1] = cnt[index];
                    index--;
                }
            }
        }


        for (int i = cnt.length - 1; i >= 0; i--) {
            if (cnt[i] == i) {
                return i;
            }
        }
        return -1;
    }
}
